package com.jun.leetcode.chapter1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 描述: 思路要清晰，其实就从中间出发去扩展
 *
 * @author Administrator
 * @create 2018-09-28 17:19
 */
public class Solution5 {
    public String longestPalindrome(String s) {
        if ( s == null || "".equals(s)){
            return "";
        }
        int len = s.length();
        int start = 0 ;
        int end = 0;
        for(int i = 0 ; i< len ; i++ ){
            int len1 = expandFromCenter(s , i , i);
            int len2 = expandFromCenter(s , i , i+1);
            int tempLen = Math.max(len1 , len2);
            if ( tempLen > end - start + 1 ){
                start = i - (tempLen - 1) / 2;
                end = i + tempLen / 2;
            }
        }
        return s.substring(start ,end+1);
    }

    private int expandFromCenter(String s, int left, int right) {
        int len = s.length();
        while ( left >= 0 && right < len && s.charAt(left ) == s.charAt(right)){
            left -- ;
            right ++;
        }
        return right - left -1;
    }


}

class Class5 {
    public static String stringToString(String input) {
        if (input == null) {
            return "null";
        }
        return input;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            String s = stringToString(line);

            String ret = new Solution5().longestPalindrome(s);

            String out = (ret);

            System.out.print(out);
        }
    }
}